package 柠檬水找零贪心算法;

/**
 * 柠檬水找零贪心算法
 * <p>
 * 在柠檬水摊上，每一杯柠檬水的售价为5美元。顾客排除购买你的产品，一次购买一杯。
 * 每位顾客只买一杯柠檬水，然后向你付5美元、10美元或20美元。必须给每个顾客正确找零。
 * 注意，一开始你手头没有任何零钱。如果你能给每位顾客正确找零，返回true，否则返回false。
 */
public class Solution {
    public static void main(String[] args) {
        System.out.println("res = " + bf(new int[]{5, 10, 20}));
        System.out.println("res = " + bf(new int[]{5, 5, 10}));


    }

    /**
     * 贪心算法
     * 找出所有答案，最后取最大的答案
     */
    private static boolean bf(int[] bills) {

        int m5 = 0;
        int m10 = 0;
        int m20 = 0;

        for (int i = 0; i < bills.length; i++) {

            int m = bills[i];
            if (m == 5) {
                m5++;
            } else if (m == 10) {
                if (m5 == 0) {
                    // 收到10元，但手上没有5元，无法找零
                    return false;
                }
                m10++;
                m5--;
            } else {
                if (m10 > 0 && m5 > 0) {
                    // 收到20元，但手上即有5元，也有10元，最优找零
                    m10--;
                    m5--;
                } else if (m5 >= 3) {
                    // 收到20元，但手上有3张以上的5元，正常找零
                    m5 -= 3;
                } else {
                    // 无法找零
                    return false;
                }
                m20++;
            }
        }

        return true;
    }


}
